package sword.offer;

/**
 * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
 *
 * @link https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class SixtyThree {
    /**
     * 股票就是低买 高卖
     * 先找到历史最低点 然后每天判断是否卖出
     * */
    class Solution {
        public int maxProfit(int[] prices) {
            if(prices.length == 0){
                return 0;
            }
            int min = prices[0];
            int profit = 0;
            for (int i = 1; i < prices.length; i++) {
                // 历史低价
                if(prices[i] < min){
                    min = prices[i];
                }
                profit = Math.max(profit, prices[i]-min);
            }
            return profit;
        }
    }

    /**
     * 使用动态规划做
     * 两个状态：持有  或  未持有
     *
     * 设dp[i][0]表示 第i天持有股后收益
     * 设dp[i][1]表示 第i天未持有后收益
     * 公式为：
     * dp[i][0] = dp[i-1][0] - prices[i]
     * dp[i][1] = prices[i] + dp[i-1][0]
     * */
    class Solution1 {
        public int maxProfit(int[] prices) {
            if(prices.length == 0){
                return 0;
            }
            int[][] dp = new int[prices.length][2];
            dp[0][0] = -prices[0];
            dp[0][1] = 0;
            for (int i = 1; i < prices.length; i++) {
                // 持有 从昨天持有的收益
                dp[i][0] = dp[i-1][0];
                // 未持有： 卖了  和  今天不动的收益
                dp[i][1] = Math.max(dp[i-1][1],prices[i] + dp[i-1][0]);
            }
            return dp[prices.length-1][1];
        }
    }
}
